#include "../head/listHelper.cpp"

// 19 remove Nth node From end of list
/**
 * 先记录链表总长度,对链表进行两次遍历
 * 时间复杂度: O(n) 空间复杂度: O(1)
 *
 */
class NthElement{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

		int length = 0;
		for(ListNode* cur = dummyHead->next; cur != NULL; cur = cur->next)
			length++;

		int k = length - n;
		assert(k >= 0);
		ListNode* cur = dummyHead;
        for(int i = 0 ; i < k ; i ++)
            cur = cur->next;

        ListNode* delNode = cur->next;
        cur->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
    }
};

int main(){
	int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int);

    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);

    head = NthElement().removeNthFromEnd(head, 2);
    printLinkedList(head);

    deleteLinkedList(head);

    return 0;
}
